Web sites, or Internet sites, often provide information, products, services, and the like to their users. Those skilled in the art are familiar with various security risks associated with a type of malicious service request known as a denial of service (DOS) attack. Denial of service attacks can be broadly classified into bandwidth attacks and resource attacks. In a bandwidth attack, the attacker disrupts a web service by supplying a plurality of service web requests (web request), from a client computer to a web server to generate a traffic over-load that clogs links or causes routers near the victim to crash. For example, if a web server serving a particular web site is configured with a wideband communication link such as a T1 link and an attacker pumps dynamically generated service requests to the web server with ten (10) T1 links, some of packets will be lost. The only way to respond to such an attack is to collaborate with the Internet Service Provider (ISP) to drop the attacker's packets at the ingress point into the network.
In a resource attack, the attacker does not use up more than your maximum bandwidth, but clogs the web server's resources so that genuine users cannot get through. Application attacks are the worst of the resource attacks because applications are usually designed to consume all the resources for only a fraction of bandwidth the server can support. If a web site is configured with a three-tiered architecture (e.g., presentation layer; a processing layer, and a database layer), the attacker can easily saturate the application server or database server by sending in a few valid fake requests. A valid fake request is a crafted valid request that does not serve the intended purpose for the service (i.e., concocted, bogus, phony). When a particular web resource is accessed more frequently than it is designed to handle, there will be a loss of service to legitimate users.
Consider a particular web server designed to handle a maximum of 4,000 content searches per second. Typically, a content search requires the web server to communicate with an application server that searches a database to retrieve the content specified by a search request received from a client computer. Further, consider that the load on the web server peaks at about 3,000 requests per second during the daytime and drops to about 500 in the early hours of morning. Users usually start with the main page and then perform a couple of searches every session. A valid search request for a nonexistent keyword in the database can be the most expensive as it misses all caches. In the worst attack, the attacker creates the search keywords dynamically. Now, consider a distributed attack is launched against the website and it starts receiving 40,000 searches per second. The website will only be able to respond to about ten percent (10%) of the search request and the chance that a valid user gets a response will be 10% and does not improve until the attack ends.
Another type of malicious service request involves a request to transmit unsolicited email (SPAM) through e-mail servers to a plurality of email addresses. The originating party (spammer) of such service request typically uses programs called bots to scour the Web and Usenet newsgroups, to harvest e-mail addresses, or may buy them in bulk from other companies. In a single email, spammers may send the same message to tens and thousands of addresses. As a result, SPAM increases the load on email servers, and drives up operational costs for companies operating such email servers, to process, filter and store emails.
Public key cryptosystems have been used to enable secure communication between parities over the Internet. For example, public key cryptosystems provide a means for parties communicating over the Internet to transmit encrypted messages to each other while making it nearly impossible for a third party to obtain and decode the transmitted messages. Most cryptosystems are built around two fundamentally hard mathematical problems: the integer factorization problem, or the discrete log problem. Factoring is the act of splitting an integer into a set of smaller integers (factors) which, when multiplied together, form the original integer. For example, the factors of 15 are 3 and 5; the factoring problem is to find 3 and 5 when given 15. Prime factorization requires splitting an integer into factors that are prime numbers; every integer has a unique prime factorization. Multiplying two prime integers together is easy, but factoring the product is much more difficult. The discrete log problem, in its most common formulation, involves solving for the exponent x in the formula a=bx, where x is an integer, and a and b belong to a finite field F. In other words, it seeks to answer the question, to what power (i.e., x) must b be raised in order to obtain a. Like the factoring problem, the discrete log problem is believed to be difficult and also to be the hard direction of a one-way function. There are other, more general, formulations as well. The most common fields used in computer cryptography are: the field of prime numbers: F(p) where p is prime and the integers 1,2, . . . p−1 are closed under multiplication and addition modulo p; the field of characteristic 2: F(2n); the field of irreducible polynomials: F(qn) where arithmetic is with respective to irreducible polynomial p(x); the Elliptic curve field: F(EC) where EC is an elliptic curve and all the elements of the field are point on the elliptic curve. The finite field F(n) is a Galois field if n is prime or the power of a large prime and all the arithmetic is executed with modular exponentiation. Evaluating the expression bx mod n is less complex than finding x where a=bx mod n. For example, it is easy compute 36 mod 17 is equal to 15 as compared to computing x is equal to 6 given 3x=15 mod 17. There are well known chaining algorithms to express x as a sum of powers of 2 and reduce the number of multiplications without generating any intermediate results greater than 2x which makes this very suitable for implementation in digital computers.
Various solutions have been proposed to handle surges due to malicious service requests when there is a common pattern in those requests. For example, service requests are frequently submitted to validation, authentication, and access controls to protect the resources and reduce the load on the targets. Thus, there is a need for managing malicious service attacks by verifying the authenticity of web request when access control based on usernames is unavailable such as when a web resource is open to the general public via the Internet.